#include <iostream>
#include <string>
using namespace std;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int T;
  for (cin >> T; T; T--) {
    int n, sum = 0;
    string s;
    long long ans = 0;
    cin >> n >> s;
    for (int i = 0; i < n; i++) {
      if (s[i] == '(') {
        ans -= i;
        sum++;
      } else if (s[i] == ')') {
        ans += i;
        sum--;
      } else {
        if (sum > 0) {
          ans += i;
          sum--;
        } else {
          ans -= i;
          sum++;
        }
      }
    }
    cout << ans << "\n";
  }
  return 0;
}